package cc.wsyw126.java.nowcoder.leetCode;

import java.util.Stack;

/**
 * Created by dp on 2017/4/20.
 * Evaluate the value of an arithmetic expression in Reverse Polish Notation.
 Valid operators are+,-,*,/. Each operand may be an integer or another expression.
 Some examples:
 ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
 */
public class EvaluateReversePolishNotation {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!tokens[i].matches("[+\\-*/]")) {
                Integer integer = Integer.valueOf(tokens[i]);
                stack.add(integer);
            } else {
                if (stack.size() <2) {
                    return 0;
                }
                Integer pop = stack.pop();
                Integer pop1 = stack.pop();
                char c = tokens[i].charAt(0);
                int i1 =0;
                switch (c) {
                    case '+':
                        i1 = pop + pop1;
                        stack.add(i1);
                        break;
                    case '-':
                        i1 = pop1 - pop;
                        stack.add(i1);
                        break;
                    case '*':
                        i1 = pop1*pop;
                        stack.add(i1);
                        break;
                    case '/':
                        i1= pop1/pop;
                        stack.add(i1);
                        break;
                }
            }
        }
        if (stack.isEmpty() || stack.size()!=1) return 0;
        return stack.pop();
    }

    public static void main(String[] args) {
        EvaluateReversePolishNotation evaluateReversePolishNotation = new EvaluateReversePolishNotation();
        int i = evaluateReversePolishNotation.evalRPN(new String[]{"3", "-4", "+"});
        System.out.println("i = " + i);
    }
}
